1. Field
This application relates to communication networks and, more particularly, to a method and apparatus for redialing a connection on a communication network.
2. Description of the Related Art
Data communication networks may include various computers, servers, hubs, switches, nodes, routers, proxies, and other devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as frames, packets, cells, or segments, between the network elements by utilizing one or more communication links. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
The various network elements on the communication network communicate with each other using predefined sets of rules, referred to herein as protocols. Different protocols are used to govern different aspects of the communication, such as how signals should be formed for transmission between network elements, various aspects of what the protocol data units should look like, and how routers should be configured to allow a protocol data unit to follow a particular path through the network.
Communication networks may be configured in multiple different topologies, such as ring-based topologies and mesh topologies. Ring-based topologies advantageously provide fast protection switching such that if a failure is experienced on a portion of the ring, traffic may be diverted the other way through the ring to minimize disruption on the network. One common ring-based topology which has been successfully deployed in North America and several other parts of the World is commonly referred to as Synchronous Optical NETwork (SONET) Bi-Directional Switched Ring (BLSR). Another similar standard that is used extensively in Europe and several other areas of the world is commonly referred to as Synchronous Data Hierarchy (SDH) Multiplex Section Shared Protection Ring (MS-SPRing).
Another common communication network topology is referred to as a mesh topology. Mesh topologies enable nodes on the mesh to communicate with multiple other nodes so that traffic is not required to be communicated to a specific node as it progresses through the network. To increase the speed at which traffic may be protection switched through a mesh network without requiring a new path to be dialed through the mesh network, it is possible to create virtual rings and reserve a portion of the bandwidth on those rings to carry protection traffic in the event of a failure. Logical restoration paths in a mesh-network are sometimes referred to as protection cycles, or p-cycles. P-cycles enable the network devices to perform fast link restoration protection without requiring notification of the source or destination nodes. Thus, in a mesh network the working path will be carried over a dialed route through the mesh network, while the restoration path will be carried over the logical ring. Mesh networks may be based on the SONET physical layer or other physical layer protocol. Other automatic protection mechanisms may be used as well depending on the underlying network architecture.
Occasionally, the automatic protection afforded by the SONET/SDH or mesh network architecture is not sufficient to maintain connectivity between points on the network. In this situation, a new path through the network will need to be determined using a process referred to herein as redial. Redialing a connection is well known in the art, and essentially requires one of the network elements handling the traffic on the network to obtain a new route through the network. This may be accomplished by extracting routing information and network topography information from a routing database and computing a desirable route through the network. In particular networks where traffic engineering is implemented to distribute traffic on the network more evenly, the network element responsible for performing the redial will have a database containing a list of nodes and links interconnecting the nodes, and an indication of the amount of bandwidth available on the links. This allows the network element to choose a route through the network that has available capacity or at least a reduced chance of congestion. As used herein, the network element configured to compute a new path will be referred to as the head-end node. The last node in the path will be referred to as the tail-end node. A given connection through the network may have multiple segments, each of which have a head-end and tail-end node. The head-end and tail-end nodes may correspond to edges of a network domain, or may otherwise be designated to perform routing functions on the network.
Routing protocols exchange available routes, and optionally bandwidths as discussed above, through the use of route advertisements. There are many different routing protocols and the manner in which information is disseminated and used may vary considerably between the various protocols. In general, however, as resources are used or released, or as links and nodes fail or are added to the network, new routing advertisements are generated and propagated through the network. Thus, when resources such as bandwidth on a link are released, the routing protocol will advertise the new availability on the link, which will be populated into the routing databases of the various network elements on the network. However, the advertisement may not be immediate and thus it may take some time for the new state of the network to converge to reflect the new availability on the released links. At the same time, however, other network elements may be dialing new connections over the link, to thereby once again reduce the capacity on the link.
FIG. 1 illustrates a communication network 10 in which network elements 12 are connected together to allow communications to occur. In the example network of FIG. 1, a connection 14 has been configured on the network through network elements [10, 3, 2, 7]. In this example, node [10] will be referred to as the head-end node and node [7] will be referred to as the tail-end node. The nodes on the network may be many different types of network elements, depending on the type of network being used, and may be for example routers, switches, or other types of common network elements.
If there is a failure on the network, such as if the link between node [3] and node [2] fails, connectivity may be restored by protection switching the traffic onto a different previously configured path on the network. For example, if the group of nodes [10, 3, 2, 6, 4] formed a ring/p-cycle, the traffic may be automatically detoured around the failed link by causing traffic to flow the other way around the ring/p-cycle. This failure recovery occurs at the transport protocol level, rather than at the routing layer. If recovery using the underlying transport technology is not possible, which may occur for a number of reasons, a new path or route through the network will need to be found for the connection. FIG. 2 illustrates an example of what the connection may look like if it was re-dialed on the network. Specifically, as shown in FIG. 2, the connection may change to be configured through network elements [10, 3, 1, 2, 7]. Other connections may be determined as well, and the invention is not limited to these particular examples.
Conventionally, when a fault on a connection was detected, the network elements adjacent the fault would send termination messages along the path toward both the head-end and the tail-end. Upon receipt by the head-end, the head-end would inspect its routing database and dial a new connection. The termination messages would be used by the nodes along the failed connection as an indication that the resources were no longer required. Thus, the nodes would release those resources and advertise their availability in subsequent routing advertisements.
Unfortunately, the delay between release of the resources and receipt by the head-end of the routing advertisement typically precluded the routing advertisement from updating the routing table of the head-end node prior to calculation of the new redial route through the network. Thus, the available resources along the previous path could not be made available to the head-end node for use on the new redial path, even though the head-end node was previously using those resources. Where the released resources are the only ones available on the network, this may preclude a connection from being established. Increasing the frequency with which routing advertisements are generated may increase the likelihood that the head-end will have the requisite updated routing information, but increases the number of route advertisements required to maintain routing databases on the network which decreases the scalability of the network. Additionally, if the routing advertisements relating to the released resources are sent to all routers on the network, other network elements may reserve the resources for other connections, thus precluding the original connection from being redialed.